import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-10-06
 * Time: 11:45
 */
class Solution21 {
    // 1.建图
    Map<Character, Set<Character>> edges = new HashMap<>();
    // 2.统计入度
    Map<Character,Integer> in = new HashMap<>();
    boolean check; //特殊情况 不用拓扑排序,直接返回即可
    public String alienOrder(String[] words) {
        int n = words.length;
        //初始化入度哈希表
        for(String s : words) {
            for(int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                in.put(ch,0);
            }
        }
        // 3.搜集信息 建图
        for(int i = 0; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                add(words[i],words[j]);
                if(check == true) {
                    return "";
                }
            }
        }
        // 4.拓扑排序
        Queue<Character> q = new LinkedList<>();
        for(char ch : in.keySet()) {
            if(in.get(ch) == 0) {
                q.add(ch);
            }
        }
        StringBuilder ret = new StringBuilder();
        while(!q.isEmpty()) {
            char t = q.poll();
            ret.append(t);

            if(!edges.containsKey(t)) continue;

            for(char ch : edges.get(t)) {
                in.put(ch,in.get(ch)-1);
                if(in.get(ch) == 0) {
                    q.add(ch);
                }
            }
        }
        // 5.判断
        for(char ch : in.keySet()) {
            if(in.get(ch) != 0) {
                return "";
            }
        }
        return ret.toString();
    }

    public void add(String s1,String s2) {
        int n = Math.min(s1.length(),s2.length());
        int i = 0;
        for(; i < n; i++) {
            char c1 = s1.charAt(i), c2 = s2.charAt(i);
            if(c1 != c2) {
                // 放进去 c1->c2
                // 判断一下是否存在，不存在先new一下
                if(!edges.containsKey(c1)) {
                    edges.put(c1,new HashSet<>());
                }
                if(!edges.get(c1).contains(c2)) {
                    edges.get(c1).add(c2);
                    in.put(c2,in.get(c2)+1);
                }
                break; //第一次找到不同就break点掉
            }
        }
        if(i == s2.length() && i < s1.length()) {
            check = true;
        }
    }
}
